/*
 * @Description:
 * @Version: 1.0
 * @Author: biao.hu
 * @Date: 2021-10-22 13:21:47
 * @LastEditors: biao.hu
 * @LastEditTime: 2021-10-28 20:23:53
 */

package List

import "fmt"

type (
	TwoWayList struct {
		H TwoWayListHeader
	}
	TwoWayListHeader struct {
		Length    int
		MaxLength int
		Next      *TwoWayListNode
		End       *TwoWayListNode
	}
	TwoWayListNode struct {
		Value  interface{}
		Next   *TwoWayListNode
		Parent *TwoWayListNode
	}
)

/**
 * @description: 验证列表
 * @param {*}
 * @return {*}
 */
func (t *TwoWayList) Validator() {
	if t.H.Length == 0 {
		panic("The length of the list is 0")
	}
}

/**
 * @description: 遍历尾插法
 * @param {int} val
 * @return {error}
 */
func (t *TwoWayList) InsertNode(val int) error {
	// 链表长度超过限定，不允许再插入
	if t.H.MaxLength == t.H.Length {
		str := fmt.Sprintf("List length out of limit, maximum length is %d, and your length is %d.", t.H.MaxLength, t.H.Length+1)
		panic(str)
	}
	node := &TwoWayListNode{Value: val}
	// 判断是否为第一节点
	if t.H.Next == nil && t.H.MaxLength > 0 {
		t.H.Next = node
		t.H.End = node
		t.H.Length++
		return nil
	}

	temp := t.H.Next
	for {
		if temp.Next == nil {
			node := &TwoWayListNode{Value: val, Parent: temp}
			temp.Next = node
			t.H.End = node
			t.H.Length++
			break
		}
		temp = temp.Next
	}
	return nil
}

/**
 * @description: 尾指针尾插法
 * @param {int} val
 * @return {error}
 */
func (t *TwoWayList) InsertNodeToEnd(val int) error {
	// 链表长度超过限定，不允许再插入
	if t.H.MaxLength == t.H.Length {
		str := fmt.Sprintf("List length out of limit, maximum length is %d, and your length is %d.", t.H.MaxLength, t.H.Length+1)
		panic(str)
	}
	node := &TwoWayListNode{Value: val, Next: nil, Parent: nil}
	// 判断是否为第一节点
	if t.H.End == nil {
		t.H.Next = node
	} else {
		node.Parent = t.H.End
		t.H.End.Next = node
	}

	t.H.End = node
	t.H.Length++

	return nil
}

/**
 * @description: 头插法
 * @param {int} val
 * @return {error}
 */
func (t *TwoWayList) InsertNodeToHeader(val int) error {
	// 链表长度超过限定，不允许再插入
	if t.H.MaxLength == t.H.Length {
		str := fmt.Sprintf("List length out of limit, maximum length is %d, and your length is %d.", t.H.MaxLength, t.H.Length+1)
		panic(str)
	}

	node := &TwoWayListNode{Value: val, Next: t.H.Next}

	if t.H.Next != nil {
		t.H.Next.Parent = node
	}

	t.H.Next = node

	// 只有一个元素时候，第一个元素即为尾节点
	if t.H.Length == 0 {
		t.H.End = t.H.Next
	}
	// 拥有两个元素，尾节点父节点为刚插入的节点
	if t.H.Length == 1 {
		t.H.End.Parent = t.H.Next
	}
	t.H.Length++

	return nil
}

/**
 * @description: 删除节点--根据值删除
 * @param {interface{}} val
 * @return {error}
 */
func (t *TwoWayList) DeleteNodeByValue(val interface{}) error {
	t.Validator()
	fmt.Println("Delete the node whose value is ", val)
	// 判断是否为第一节点
	if t.H.Next.Value == val {
		t.H.Next.Next.Parent = nil
		t.H.Next = t.H.Next.Next
		t.H.Length--
		_ = t.DeleteNodeByValue(val)
	}
	p := t.H.Next
	// 保存删除前节点的上一节点
	parent := p
	for {
		if p.Value == val {
			p.Next.Parent = parent
			parent.Next = p.Next
			t.H.Length--
		}
		parent = p
		p = p.Next
		if p == nil {
			break
		}
	}
	return nil
}

/**
 * @description: 删除节点--根据位置删除,下标从0开始
 * @param {int} index
 * @return {error}
 */
func (t *TwoWayList) DeleteNodeByIndex(index int) error {
	t.Validator()
	if index < 0 || index > t.H.Length {
		panic("The location you want to delete is illegal！")
	}
	fmt.Println("Delete the node whose index is ", index)
	// 判断是否为第一个元素
	if index == 0 {
		t.H.Next.Next.Parent = nil
		t.H.Next = t.H.Next.Next
		t.H.Length--
	} else {
		count := 0
		p := t.H.Next
		// 保存删除前节点的上一节点
		parent := p
		for {
			// 如果删除的位置找到
			if count == index {
				p.Next.Parent = parent
				parent.Next = p.Next
				t.H.Length--
				break
			}
			parent = p
			p = p.Next
			count++
		}
	}
	return nil
}

/**
 * @description: 正叙
 * @param {*}
 * @return {*}
 */
func (t *TwoWayList) Show() {
	// 判断链表是否为空
	t.Validator()
	str := fmt.Sprintf("Header: [len(%d), max(%d), index_start(%d), index_end(%d)]", t.H.Length, t.H.MaxLength, t.H.Next.Value, t.H.End.Value)
	fmt.Print(str)
	p := t.H.Next
	for {
		// 如果下一节点不存在，则退出
		if p == nil {
			break
		}
		fmt.Print("->")
		fmt.Print("Node:", p.Value)
		p = p.Next
	}
	fmt.Println()
}

/**
 * @description: 倒叙
 * @param {*}
 * @return {*}
 */
func (t *TwoWayList) BackShow() {
	// 判断链表是否为空
	t.Validator()
	p := t.H.End
	for {
		// 如果下一节点不存在，则退出
		if p == nil {
			break
		}
		fmt.Print("Node:", p.Value)
		fmt.Print("->")
		p = p.Parent
	}
	str := fmt.Sprintf("Header: [len(%d), max(%d), index_start(%d), index_end(%d)]", t.H.Length, t.H.MaxLength, t.H.Next.Value, t.H.End.Value)
	fmt.Print(str)
	fmt.Println()
}

/**
 * @description: 该方法放在main方法里面运行
 * @param {*}
 * @return {*}
 */
func Run() {
	t := TwoWayList{H: TwoWayListHeader{Length: 0, Next: nil, MaxLength: 100, End: nil}}
	for i := 0; i < 20; i++ {
		// 遍历型尾插法
		//_ = t.InsertNode(i)
		// 通过尾指针尾插法
		//_ = t.InsertNodeToEnd(i)
		// 头插法
		_ = t.InsertNodeToHeader(i)
	}
	// 通过值删除节点元素
	//_ = t.DeleteNodeByValue(1)
	// 通过下标删除元素
	//_=t.DeleteNodeByIndex(1)
	t.Show()
	t.BackShow()
}
